线性表的应用举例（约瑟夫环问题）

线性表的应⽤举例（约瑟夫环问题）

约瑟夫环问题的⼀种描述是：编号为1,2，…，n的n个⼈按顺时针⽅向围坐⼀圈，每个⼈持有⼀个密码（正整数）。⼀开始⼈选⼀个正整数

作为报数上限m，从第⼀个⼈开始按顺时针⽅向⾃1开始顺序报数，报到m时停⽌报数。报m的⼈出列，将它的密码作为新的m值，从它的

顺时针⽅向的下⼀个⼈开始重新从1报数，如此下去，直⾄全部⼈出列为⽌。最后按照出列的顺序输出各⼈的编号。

数据结构

typedef

struct

 Node

{

int

 data

;

/*

存储⼈数

*/

int

 password

;

/*

存储的每⼈所对应的密码

*/

struct

 Node 

*

next

;

}

LinkList

;

其主要的数据类型为⽆头结点的单向循环链表。

/*

约瑟夫环源程序

*/

#

include

"stdio.h"

#

include

"stdlib.h"

#

define

 MAXPV 20 

//

每个⼈最⼤密码值为

20 

#

define

 MAXNUM 30 

//

需要处理的最多⼈数为

30 

#

define

 MAXFV 10 

//

初始查找的上限值为

10 

typedef

struct

 LinkList

{

int

 data

;

int

 password

;

struct

 LinkList 

*

next

;

}

 LinkList

;

/*

函数声明

*/

 LinkList 

*

CreatList

();

int

InitList

(

LinkList 

*

,

int

);

int

GetPassword

();

int

GetPersonNumber

();

int

GetFirstCountValue

();

int

GetOutputOrder

(

 LinkList

*

,

int

,

int

,

int

*

);

int

printResult

(

int

*

,

int

);

 LinkList 

*

CreatList

()

{

/*

初始化单链表函数

*/

  LinkList 

*

L

;

  L

=

(

LinkList 

*

)

malloc

(

sizeof

(

LinkList

));

if

(

L

==

NULL

)

{

printf

(

"

分配内存失败！

"

);

exit

(

1

);

}

return

 L

;

}

int

InitList

(

LinkList 

*

L

,

int

 personNumber

)

{

/*

建⽴单循环链表函数

*/

  LinkList 

*

p

,

*

q

;

int

 i

;

  p

=

L

;

  p

->

data

=

1

;

  p

->

password

=

GetPassword

();

for

(

i

=

2

;

i

password

=

GetPassword

();